﻿public class Solution {
    public int MaxProfit(int[] prices, int fee) 
    {
        // 持有，未持有 -- 卖出时交手续费
        int[,] dp = new int[prices.Length, 2];
        dp[0, 0] = -prices[0];

        for (int i = 1; i < prices.Length; i++)
        {
            dp[i, 0] = Math.Max(dp[i - 1, 0], dp[i - 1, 1] - prices[i]);
            dp[i, 1] = Math.Max(dp[i - 1, 1], dp[i - 1, 0] + prices[i] - fee);
        }

        return dp[prices.Length - 1, 1];
    }

    public static void Main(string[] args)
    {
        int[] prices = [1, 3, 2, 8, 4, 9];
        int fee = 2;

        Solution solution = new Solution();
        int res = solution.MaxProfit(prices, fee);
        Console.WriteLine(res);
    }
}